package cn.cxq.learning.search;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Client {

    @Test
    public void testLinearSearch() {

        int[] arr = {1, 2, -1, 3, 56, 100, 78, 324, -12, -1023};


        printResult(LinearSearch.search(arr, -1023));
        printResult(LinearSearch.search(arr, 1201));
    }

    @Test
    public void testBinarySearch() {

        int[] arr = {-1023, -12, -1, 1, 2, 3, 56, 78, 100, 324};

        printResult(BinarySearch.recurSearch(arr, 78));
        printResult(BinarySearch.recurSearch(arr, 1201));

        printResult(BinarySearch.search(arr, 78));
        printResult(BinarySearch.search(arr, 1201));

        int[] arr2 = initIntArray(10000000);

        System.out.println("二分查找递归10000000个数据测试：");
        long pre1 = System.currentTimeMillis();
        printResult(BinarySearch.recurSearch(arr2, 100));
        long post1 = System.currentTimeMillis();
        System.out.println("查找用时：" + (post1 - pre1) + " ms");

        System.out.println("二分查找非递归10000000个数据测试：");
        long pre2 = System.currentTimeMillis();
        printResult(BinarySearch.search(arr2, 100));
        long post2 = System.currentTimeMillis();
        System.out.println("查找用时：" + (post2 - pre2) + " ms");
    }

    private void printResult(int index) {
        if (index == -1) System.out.println("未找到该数字");

        else System.out.println("该数字在数组中的下标为：" + index);
    }

    public int[] initIntArray(int num) {
        int[] arr = new int[num];
        for (int i = 0; i < arr.length; i++) arr[i] = (int) (Math.random() * num * 10);
        Arrays.sort(arr);
        return arr;
    }

    @Test
    public void testInterpolationSearch() {
        int[] arr = {-1023, -12, -1, 1, 2, 3, 56, 78, 100, 324};

        printResult(InterpolationSearch.recurSearch(arr, 78));
        printResult(InterpolationSearch.recurSearch(arr, 1201));

        printResult(InterpolationSearch.search(arr, 78));
        printResult(InterpolationSearch.search(arr, 1201));

        int[] arr2 = initIntArray(10000000);

        System.out.println("二分查找递归\n" +
                "10000000个数据测试：");
        long pre1 = System.currentTimeMillis();
        printResult(InterpolationSearch.recurSearch(arr2, 100));
        long post1 = System.currentTimeMillis();
        System.out.println("查找用时：" + (post1 - pre1) + " ms");

        System.out.println("二分查找非递归\n" +
                "10000000个数据测试：");
        long pre2 = System.currentTimeMillis();
        printResult(InterpolationSearch.search(arr2, 100));
        long post2 = System.currentTimeMillis();
        System.out.println("查找用时：" + (post2 - pre2) + " ms");
    }

    @Test
    public void testFibonacciSearch() {
        int[] arr = {-1023, -12, -1, 1, 2, 3, 56, 78, 100, 324};

        printResult(FibonacciSearch.search(arr, 78));
        printResult(FibonacciSearch.search(arr, 1500));

        int[] arr2 = initIntArray(10000000);

        System.out.println("斐波那契查找\n" +
                "10000000个数据测试：");
        long pre2 = System.currentTimeMillis();
        printResult(FibonacciSearch.search(arr2, 100));
        long post2 = System.currentTimeMillis();
        System.out.println("查找用时：" + (post2 - pre2) + " ms");
    }

    /**
     * arraylist集合的remove方法：
     * 1.当参数是一个对象的时候，集合会从头到尾遍历集合删除掉第一个与该对象值相等的元素。
     * 2.当参数是一个下标的时候，删除对应下标的元素
     */
    @Test
    public void testArrayList() {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(0);
        list.add(1);
        list.remove(1);
        list.remove(new Integer(1));
        list.forEach(item -> System.out.println(item));
    }

    @Test
    public void testHashSearch() {

        int[] hashList = HashSearch.convertIntoHashList(new int[]{18, 72, 73, 45, -12, 534, 21654, -234, -2342, 73});
        System.out.println(Arrays.toString(hashList));

        printResult(HashSearch.search(hashList, 18));
        printResult(HashSearch.search(hashList, 16));
        printResult(HashSearch.search(hashList, -2342));

        int[] arr = initIntArray(1000000);
        int[] hashList2 = HashSearch.convertIntoHashList(arr);

        System.out.println("哈希查找\n" +
                "1000000个数据测试：");
        long pre1 = System.currentTimeMillis();
        printResult(FibonacciSearch.search(hashList2, 100));
        long post1 = System.currentTimeMillis();
        System.out.println("查找用时：" + (post1 - pre1) + " ms");
    }

}
